using BepuUtilities.Memory;
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace BepuUtilities.Collections
{
    /// <summary>
    /// 支持添加、删除和包含操作的唯一索引集合。
    /// </summary>
    public struct IndexSet
    {
        /// <summary>
        /// 因为我们只需要支持添加、删除和包含检查,并且保证索引是唯一的,
        /// 我们可以只使用压缩的位域。每个位代表一个索引的包含状态。
        /// </summary>
        /// <remarks> 
        /// 在最坏的情况下,它可以增长到(indexCount/8)字节数,但这比使用字典或集合要小得多。
        /// 16384具身体只需要2KB。即使你有1000个批次,全部都是这个大小,这也是一个相当无关紧要的存储量。
        /// (需要说明的是,1000批次是一个疯狂的病理数字。大多数模拟的批次将少于20批。)
        /// </remarks>
        public Buffer<ulong> Flags;

        const int shift = 6;
        const int mask = 63;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static int GetBundleCapacity(int count)
        {
            return (count + mask) >> shift;
        }

        public IndexSet(BufferPool pool, int initialCapacity)
        {
            // 请记住,这些捆绑包有64面旗帜宽。默认值128最多支持8192个索引,无需调整大小.
            Flags = new Buffer<ulong>();
            InternalResize(pool, initialCapacity);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void InternalResize(BufferPool pool, int capacity)
        {
            InternalResizeForBundleCount(pool, GetBundleCapacity(capacity));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void InternalResizeForBundleCount(BufferPool pool, int bundleCapacity)
        {
            var copyRegionLength = Math.Min(bundleCapacity, Flags.Length);
            pool.ResizeToAtLeast(ref Flags, bundleCapacity, copyRegionLength);
            // 因为不能保证池的数据是干净的,而索引依赖于它是干净的,所以我们必须清除复制区域之外的所有内存。
            if (Flags.Length > copyRegionLength)
                Flags.Clear(copyRegionLength, Flags.Length - copyRegionLength);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Contains(int index)
        {
            var packedIndex = index >> shift;
            return packedIndex < Flags.Length && (Flags[packedIndex] & (1ul << (index & mask))) > 0;
        }

        /// <summary>
        /// 获取批处理是否可以保存指定的索引。
        /// </summary>
        /// <param name="indexList">要在批中检查的索引列表。</param>
        /// <return>如果集合中没有任何索引,则为True,否则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public unsafe bool CanFit(Span<int> indexList)
        {
            for (int i = 0; i < indexList.Length; ++i)
            {
                if (Contains(indexList[i]))
                {
                    return false;
                }
            }
            return true;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void AddUnsafely(int index, int bundleIndex)
        {
            ref var bundle = ref Flags[bundleIndex];
            var slot = 1ul << (index & mask);
            Debug.Assert((bundle & slot) == 0, "Cannot add if it's already present!");
            // 分支停止不会改变结果的单个指令没有多大意义。
            bundle |= slot;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Add(int index, BufferPool pool)
        {
            var bundleIndex = index >> shift;
            if (bundleIndex >= Flags.Length)
            {
                // 请注意,捆绑索引可能大于当前容量的两倍,因为不保证追加索引。
                InternalResizeForBundleCount(pool, 1 << SpanHelper.GetContainingPowerOf2(bundleIndex + 1));
            }
            AddUnsafely(index, bundleIndex);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void AddUnsafely(int index)
        {
            AddUnsafely(index, index >> shift);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Remove(int index)
        {
            Debug.Assert((Flags[index >> shift] & (1ul << (index & mask))) > 0, "If you try to remove a index, it should be present.");
            Flags[index >> shift] &= ~(1ul << (index & mask));
        }

        public void Clear()
        {
            Flags.Clear(0, Flags.Length);
        }

        public void EnsureCapacity(int indexCapacity, BufferPool pool)
        {
            if ((Flags.Length << shift) < indexCapacity)
            {
                InternalResize(pool, indexCapacity);
            }
        }

        // 当我们暴露压缩并调整大小时,使用它需要小心。例如,缩小到超过当前的Body索引大小将是错误的。
        public void Compact(int indexCapacity, BufferPool pool)
        {
            var desiredBundleCount = BufferPool.GetCapacityForCount<ulong>(GetBundleCapacity(indexCapacity));
            if (Flags.Length > desiredBundleCount)
            {
                InternalResizeForBundleCount(pool, desiredBundleCount);
            }
        }
        public void Resize(int indexCapacity, BufferPool pool)
        {
            var desiredBundleCount = BufferPool.GetCapacityForCount<ulong>(GetBundleCapacity(indexCapacity));
            if (Flags.Length != desiredBundleCount)
            {
                InternalResizeForBundleCount(pool, desiredBundleCount);
            }
        }
        /// <summary>
        /// 释放内部缓冲区。
        /// </summary>
        /// <remarks>The instance can be reused after a Dispose if EnsureCapacity or Resize is called.
        /// 考虑到实例是值类型,这有点没有意义,但是嘿,您不需要重新创建另一个实例,这是很重要的。</regations>
        public void Dispose(BufferPool pool)
        {
            Debug.Assert(Flags.Length > 0, "Cannot double-dispose.");
            pool.Return(ref Flags);
            Flags = new Buffer<ulong>();
        }
    }
}
